package uestc.lj.basic.tree;

/**
 * 判断一棵二叉树是否是平衡二叉树
 *
 * @Author:Crazlee
 * @Date:2021/11/23
 */
public class Code07_IsBalancedTree {
	public static class Node {
		public int value;
		public Node left;
		public Node right;

		public Node(int data) {
			this.value = data;
		}
	}

	public static class ReturnType {
		public boolean isBalanced;
		public int height;

		public ReturnType(boolean isBalanced, int height) {
			this.isBalanced = isBalanced;
			this.height = height;
		}
	}

	public static boolean isBalancedTree(Node head) {
		return process(head).isBalanced;
	}

	private static ReturnType process(Node head) {
		if (head == null) {
			return new ReturnType(true, 0);
		}
		ReturnType left = process(head.left);
		ReturnType right = process(head.right);

		int height = Math.max(left.height, right.height) + 1;
		boolean isBalanced = left.isBalanced && right.isBalanced && Math.abs(left.height - right.height) < 2;
		return new ReturnType(isBalanced, height);
	}
}
